package com.chj.jz.dp.class02;

//https://www.lintcode.com/problem/unique-paths-ii/description
public class Code01_UniquePathsII {
	/**
	 * @param obstacleGrid:
	 *            A list of lists of integers
	 * @return: An integer
	 */
	public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
		// write your code here
		int m = obstacleGrid.length;
		if (m == 0) {
			return 0;
		}

		int n = obstacleGrid[0].length;
		if (n == 0) {
			return 0;
		}

		int[][] f = new int[m][n];
		int i, j;
		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if (obstacleGrid[i][j] == 1) {
					f[i][j] = 0;
					continue;
				}

				if (i == 0 && j == 0) {
					f[i][j] = 1;
					continue;
				}

				f[i][j] = 0;
				if (i > 0) {
					f[i][j] += f[i - 1][j];
				}

				if (j > 0) {
					f[i][j] += f[i][j - 1];
				}
			}
		}

		return f[m - 1][n - 1];
	}
	
	public static void main(String[] args) {
		{
			int[][] arr = new int[][] {{0}};
			System.out.println(uniquePathsWithObstacles(arr));
		}
		{
			int[][] arr = new int[][] {{0,0,0},{0,1,0},{0,0,0}};
			System.out.println(uniquePathsWithObstacles(arr));
		}
	}

}
